package com.example.leetcode.trainingcamp.week9.sunday;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 * 节点间通路。给定有向图，设计一个算法，找出两个节点之间是否存在一条路径。
 *
 * 示例1:
 *
 *  输入：n = 3, graph = [[0, 1], [0, 2], [1, 2], [1, 2]], start = 0, target = 2
 *  输出：true
 * 示例2:
 *
 *  输入：n = 5, graph = [[0, 1], [0, 2], [0, 4], [0, 4], [0, 1], [1, 3], [1, 4], [1, 3], [2, 3], [3, 4]], start = 0, target = 4
 *  输出 true
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/route-between-nodes-lcci
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class Offer04_01 {

    public boolean findWhetherExistsPath(int n, int[][] graph, int start, int target) {
        List<List<Integer>> list = new ArrayList<>(n);
        for (int i =0;i<n;i++){
            list.add(new ArrayList<>());
        }
        for (int[] g: graph) {
            list.get(g[0]).add(g[1]);
        }
        boolean[]visit = new boolean[n];
        Queue<Integer> queue = new LinkedList<>();
        queue.add(start);
        while (!queue.isEmpty()){
            Integer poll = queue.poll();
            for (int i = 0;i<list.get(poll).size();i++){
                Integer integer = list.get(poll).get(i);
                if (!visit[integer]){
                    visit[integer] = true;
                    if (integer == target) return true;
                }
                queue.add(integer);
            }
        }
        return false;
    }
}
